package practice7;

import java.util.Arrays;

/**
 * ## 问题描述
 * 有`n`个元素的数组，元素由`[0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]`组成；
 *
 * 现在想从数组中选择一段连续的区间，得到尽可能大的乘积；
 *
 * ## 输入格式
 * 每个样例有两行；
 * 第一行是整数`n`，表示数组长度；（$1≤n≤10000$）
 * 第二行是`n`个整数，整数取值为`[0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]`；
 *
 * ## 输出格式
 * 每个样例一行，输出整数`x`和`y`，表示乘积最大的区间`[x, y]`；
 * 如果有多个答案，输出`x`尽可能小的答案；如果仍有多个答案，输出`y`尽可能小的答案；
 *
 * ## 输入样例1
 * ```
 * 5
 * 1 2 4 0 8
 * ```
 *
 * ## 输出样例1
 *
 * 1 3
 *
 *
 * ## 输入样例2
 * ```
 * 7
 * 1 2 4 8 0 256 0
 * ```
 *
 * ## 输出样例2
 *
 * 6 6
 *
 *
 * ## 样例解释
 * 样例1，区间`[1, 3]`和`[5, 5]`的乘积均为8，是最大的乘积；`[1, 3]`的左区间更小，所以输出`[1, 3]`;
 * 样例2，区间`[6, 6]`的乘积为`256`，是最大的乘积；
 *
 * ## 数据范围
 * $
 * 1≤n≤10000
 * $
 */
public class Main {
    public static int[] solution(int n, int[] data) {
        // Edit your code here
        //int maxProduct = 0;
        long maxProduct = 0;
        int start = 0; // 子数组开始位置
        int end = 0;   // 子数组结束位置
        int tempStart = 0; // 当前考察的子数组开始位置

        for (int i = 0; i < n; i++) {
            if (data[i] == 0) {
                // 如果遇到0，则重置临时开始位置到下一个元素
                tempStart = i + 1;
            } else {
                // 计算当前考察子数组的乘积
                //int product = 1;
                long product = 1;
                for (int j = tempStart; j <= i; j++) {
                    product *= data[j];
                }
                // 检查是否找到了更大的乘积
                if (product > maxProduct ||
                        (product == maxProduct && (tempStart < start || (tempStart == start && i < end)))) {
                    maxProduct = product;
                    start = tempStart;
                    end = i;
                }
            }
        }

        // 返回子数组的边界
        return new int[]{start + 1, end + 1}; // 题目要求输出下标从1开始


        //return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        // Add your test cases here
        //System.out.println(Arrays.equals(solution(5, new int[]{1, 2, 4, 0, 8}), new int[]{1, 3}));
        //System.out.println(Arrays.equals(solution(7, new int[]{1, 2, 4, 8, 0, 256, 0}), new int[]{6, 6}));
        System.out.println(Arrays.equals(solution(11, new int[]{1024,0,2,1,0,2,128,512,4,256,256}), new int[]{6, 11}));

    }
}
